home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / ptpoly_weiler / pt_poly.c < prev   
Encoding:
C/C++ Source or Header  |  1995-02-06  |  2.4 KB  |  73 lines
  1. /*
  2.  * C code from the article
  3.  * "An Incremental Angle Point in Polygon Test"
  4.  * by Kevin Weiler, kjw@autodesk.com
  5.  * in "Graphics Gems IV", Academic Press, 1994
  6.  */
  7.  
  8. #include "polygon.h"
  9.  
  10.     /* quadrant id's, incremental angles, accumulated angle values */
  11. typedef short quadrant_type;
  12.  
  13.     /* result value from point in polygon test */
  14. typedef enum pt_poly_relation {INSIDE, OUTSIDE} pt_poly_relation;
  15.  
  16.     /* determine the quadrant of a polygon point
  17.        relative to the test point */
  18. #define quadrant(vertex, x, y) \
  19.   ( (vertex->x > x) ? ((vertex->y > y) ? 0 : 3) : ( (vertex->y > y) ? 1 : 2) )
  20.  
  21.     /* determine x intercept of a polygon edge
  22.        with a horizontal line at the y value of the test point */
  23. #define x_intercept(pt1, pt2,  yy) \
  24.   (pt2->x - ( (pt2->y - yy) * ((pt1->x - pt2->x) / (pt1->y - pt2->y)) ) )
  25.  
  26.     /* adjust delta */
  27. #define adjust_delta(delta, vertex, next_vertex, xx, yy)        \
  28.   switch (delta) {                            \
  29.         /* make quadrant deltas wrap around */            \
  30.     case  3:    delta = -1; break;                    \
  31.     case -3:    delta =     1; break;                    \
  32.         /* check if went around point cw or ccw */            \
  33.     case  2: case -2: if (x_intercept(vertex, next_vertex, yy) > xx)    \
  34.             delta =  - (delta);                    \
  35.         break;                            \
  36.     }
  37.  
  38.     /* determine if a test point is inside of or outside of a polygon */
  39.     /* polygon is "poly", test point is at "x","y" */
  40. pt_poly_relation
  41. point_in_poly(polygon_ptr poly, double x, double y)
  42. {
  43.   vertex_ptr  vertex, first_vertex, next_vertex;
  44.   quadrant_type quad, next_quad, delta, angle;
  45.  
  46.         /* initialize */
  47.   vertex = NULL;    /* because polygon_get_vertex is a macro */
  48.   vertex = first_vertex = polygon_get_vertex(poly,vertex);
  49.   quad = quadrant(vertex, x, y);
  50.   angle = 0;
  51.         /* loop on all vertices of polygon */
  52.   do {
  53.     next_vertex = polygon_get_vertex(poly,vertex);
  54.         /* calculate quadrant and delta from last quadrant */
  55.     next_quad = quadrant(next_vertex, x, y);
  56.     delta = next_quad - quad;
  57.     adjust_delta(delta,vertex,next_vertex,x,y);
  58.         /* add delta to total angle sum */
  59.     angle = angle + delta;
  60.         /* increment for next step */
  61.     quad = next_quad;
  62.     vertex = next_vertex;
  63.     } while (vertex != first_vertex);
  64.  
  65.         /* complete 360 degrees (angle of + 4 or -4 ) means inside */
  66.   if ((angle == +4) || (angle == -4)) return INSIDE; else return OUTSIDE;
  67.  
  68.         /* odd number of windings rule */
  69.   /* if (angle & 4) return INSIDE; else return OUTSIDE; */
  70.         /* non-zero winding rule */
  71.   /* if (angle != 0) return INSIDE; else return OUTSIDE; */
  72. }
  73.